
// 516.最长回文子序列
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        // 使用动态规划来解决 , 使用一个二维的DP表来实现
        int n = s.size();
        vector<vector<int>>  dp(n,vector<int>(n,1));   // dp[i][j] 表示[j,i]中回文序列的
        int ret = 1;
        for(int i = 1 ; i < n ; i++)
        {
            for(int j = i - 1; j >= 0 ; j--)
            {
                if(s[i] == s[j] && j + 1 == i) dp[i][j] = 2;
                else if(s[i] == s[j]) dp[i][j] = dp[i - 1][j + 1] + 2; 
                else if(s[i] != s[j]) dp[i][j] = max(dp[i][j + 1],dp[i - 1][j]);
                ret = max(ret , dp[i][j]);
            }
        }
        return ret;
    }
};